/**************************************************************************
*   Copyleft 2009 by        											  *
*	Iwanicki Krzysztof													  *
*   <www.gamma.mini.pw.edu.pl/~iwanickik>		                          *
*                                                                         *
*   This program is free software; you can redistribute it and/or modify  *
*   it under the terms of the GNU General Public License as published by  *
*   the Free Software Foundation; either version 2 of the License, or     *
*   (at your option) any later version.                                   *
*                                                                         *
*   This program is distributed in the hope that it will be useful,       *
*   but WITHOUT ANY WARRANTY; without even the implied warranty of        *
*   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         *
*   GNU General Public License for more details.                          *
***************************************************************************/
#ifndef __VHASH_MAP_H__
#define __VHASH_MAP_H__
#include "./vString.h"
#include "./vPair.h"
#include "../Macros/vMemoryMacros.h"

namespace Vendetta {
	/*! \class Hash array.
	 *	\brief Grows dynamically when it should.
	 */
	template <class TI, class TV> class vHashMap {

	private:

		/*! \brief Returns hash key for integer value.
		 *
		 *	\param key Integer value.
		 *	\return Hash value.
		 */
		static vInt HashKey(const vInt key) {
			return key;
		}

		/*! \brief Returns hash key for long value.
		 *
		 *	\param key Long value.
		 *	\return Hash value.
		 */
		static vInt HashKey(const vLong key) {
			return key;
		}

		/*! \brief Returns hash key for short value.
		 *
		 *	\param key Short value.
		 *	\return Hash value.
		 */
		static vInt HashKey(const vShort key) {
			return key;
		}

		/*! \brief Returns hash key for char value.
		 *
		 *	\param key Char value.
		 *	\return Hash value.
		 */
		static vInt HashKey(const vChar key) {
			return key;
		}

		/*! \brief Returns hash key for string.
		 *
		 *	\param key String.
		 *	\return Hash value.
		 */
		static vInt HashKey(const vChar* key) {
			if (!key) {
				return 0;
			}
			vInt value = 0;
			vInt i = 0;
			while (key[i] != '\0') {
				value += key[i];
				i++;
			}
			return value;
		}

		/*! \brief Returns hash key for string.
		 *
		 *	\param key String.
		 *	\return Hash value.
		 */
		static vInt HashKey(const vString& key) {
			if (!key.Length()) {
				return 0;
			}
			vInt value = 0;
			for (vUInt i = 0; i < key.Length(); i++) {
				value += key.At(i);
				i++;
			}
			return value;
		}

		/*! \brief Returns hash key for string.
		 *
		 *	\param key String.
		 *	\return Hash value.
		 */
		static vInt HashKey(const std::string& key) {
			if (!key.length()) {
				return 0;
			}
			vInt value = 0;
			for (vUInt i = 0; i < key.length(); i++) {
				value += key.at(i);
				i++;
			}
			return value;
		}

	private:

		/*! \class vElement.
		 *	\brief Single hash list element.
		 */
		class vElement {
		public:
			/*! \brief Constructor.
			 *	Initializes key with given key.
			 *
			 *	\param key Key.
			 */
			vElement(const TI &key): Next(vNull), Key(key) { }

			/*! \brief Constructor.
			 *
			 *	Initializes key with given key and links it to list.
			 *
			 *	\param key Key.
			 *	\param list List.
			 */
			vElement(const TI &key, vElement** list): Next(vNull), Key(key)	{
				Next = *list;
				*list = this;
			}

			/*! \brief Constructor.
			 *
			 *	Initializes key with given key, value with given value
			 *	and links it to list.
			 *
			 *	\param key Key.
			 *	\param value Value.
			 *	\param list List.
			 */
			vElement(const TI &key, const TV &value, vElement** list): Next(vNull),	Key(key), Value(value) {
				Next = *list;
				*list = this;
			}

			TI			Key;		//! Key
			TV			Value;		//! Value
			vElement*	Next;		//! Link to next element on the list
		};

	public:

		/*! \brief Constructor.
		 *	
		 */
		vHashMap(): mSize(0), mpArray(vNull), mNum(0) { }

		/*! \brief Constructor.
		 *
		 *	Initializes hash array with given size.
		 *
		 *	\param size wanted array size
		 */
		vHashMap(const vInt size): mSize(0), mpArray(vNull), mNum(0) {
			rehash(size);
		}

		/*! \brief Copying constructor.
		 *
		 *
		 *	\param hashArray other hash array to copy data from.
		 */
		vHashMap(const vHashMap &hashArray): mSize(0), mpArray(vNull), mNum(0)	{
			*this = hashArray;
		}

		/*! \brief Destructor.
		 *
		 *	Kills all data.
		 */
		~vHashMap()	{
			Clear();
		}
		
		/*! \brief Assign operator.
		 *
		 *
		 *	\param hashArray Other hash array to assign data from.
		 */
		vHashMap& operator=(const vHashMap &hashArray)	{
			if (this != &hashArray) {
				Clear();
				mSize = hashArray.mSize;
				mNum = hashArray.mSize;
				for (vInt i = 0; i < hashArray.mSize; i++) {
					mpArray[i] = vNull;
				}
				for (vInt i = 0; i < hashArray.mSize; i++) {
					if (hashArray.mpArray[i]) {
						vElement *pTmp = hashArray.mpArray[i];
						while (pTmp) {
							new vElement(pTmp->Key, pTmp->Value, &mpArray[i]);
							pTmp = pTmp->Next;
						}
					}
				}
			}
			
			return *this;
		}

		/*! \brief Returns size of hash array
		 *
		 *
		 *	\return Size of hash array.
		 */
		vUInt Size() const {
			return mNum;
		}

		/*! \brief Empties hash array.
		 */
		vVoid Clear() {
			vElement** arrToDel = mpArray;
			vElement* tmp;
			for (vInt i = mSize - 1; i >= 0; i--) {
				while (mpArray[i]) {
					tmp = mpArray[i];
					mpArray[i] = mpArray[i]->Next;
					vDelete(tmp);
				}
			}
			mSize = 0;
			mNum = 0;
			vDeleteArray(mpArray);
		}

		/*! \brief Brackets operator.
		 *
		 *	Crashes if given key isn't present in hash table, so don't use it
		 *	in case you're not really sure element you ask for exists.
		 *
		 *	\param key Key.
		 *	\return Value at key.
		 */
		TV &operator [] (const TI &key) const {
			V_CHECK(mSize > 0);
			const vInt hashKey = HashKey(key) & (mSize - 1);
			vElement* tmp = mpArray[hashKey];
			while (tmp) {
				if (tmp->Key == key) {
					return tmp->Value;
				}
				tmp = tmp->Next;
			}
			V_CHECK(false);		// We shouldn't arrive here

			return tmp->Value;	// Return whatever and crash.
		}

		const vPair<TI, TV> Element(vUInt uiIndex) {
			vIterator iter(*this);
			vUInt i = 0;

			while (i < uiIndex && iter) {
				++iter;
				i++;
			}

			if (!iter) {
				throw vFatalException("Index out of bounds.In vHashMap::Element.");
			} else {
				return vPair<TI, TV>(iter.Key(), iter.Value());
			}
		}

		/*! \brief Tells whether value at key exists.
		 *
		 *
		 *	\param key Key.
		 *	\return True if value at key exists, false otherwise.
		 */
		vBool Contains(const TI &key) const {
			if (mSize == 0) {
				return false;
			}
			const vInt hashKey = HashKey(key) & (mSize - 1);
			vElement* tmp = mpArray[hashKey];
			while (tmp) {
				if (tmp->Key == key) {
					return true;
				}
				tmp = tmp->Next;
			}
			return false;
		}

		/*! \brief Puts element into hash array (optionally only changes value at key).
		 *
		 *
		 *	\param key Key.
		 *	\param value value to be set at Key.
		 */
		vVoid Insert(const TI &key, const TV &value) {
			vInt hashKey;
			if (mSize > 0) {
				hashKey = HashKey(key) & (mSize - 1);
				vElement* tmp = mpArray[hashKey];
				while (tmp) {
					if (tmp->Key == key) {
						tmp->Value = value;
						return;
					}
					tmp = tmp->Next;
				}
			}
			mNum++;
			if (mNum > mSize) {
				rehash(mNum);
				hashKey = HashKey(key) & (mSize - 1);
			}
			new vElement(key, value, &mpArray[hashKey]);
		}

		/*! \brief Puts element into hash array (optionally only changes value at key).
		*
		*
		*	\param key Key.
		*	\param value value to be set at Key.
		*/
		vHashMap& operator<<(const vPair<TI, TV> value) {
			Insert(value.First, value.Second);

			return *this;
		}

		/*! \brief Removes element at key and returns its value.
		 *
		 *
		 *	\param key Key to remove element at.
		 *	\param value Value to be returned in case of success.
		 *	\return True if element with key existed (that is removal was successful).
		 */
		vBool Remove(const TI &key, TV &value) {
			V_CHECK(mSize > 0);
			const vInt hashKey = HashKey(key) & (mSize - 1);
			vElement* tmp = mpArray[hashKey];
			vElement* prev = vNull;
			while (tmp) {
				if (tmp->Key == key) {
					if (prev) {
						prev->Next = tmp->Next;
					} else {
						mpArray[hashKey] = vNull;
					}
					value = tmp->Value;
					vDelete( tmp );
					mNum--;
					return true;
				}
				prev = tmp;
				tmp = tmp->Next;
			}
			return false;
		}

		/*! \brief Removes element at key.
		 *
		 *
		 *	\param key Key to remove element at.
		 *	\return True if element with key existed (that is removal was successful).
		 */
		vBool Remove(const TI &key)	{
			V_CHECK(mSize > 0);
			const vInt hashKey = HashKey(key) & (mSize - 1);
			vElement* tmp = mpArray[hashKey];
			vElement* prev = vNull;
			while (tmp) {
				if (tmp->Key == key) {
					if (prev) {
						prev->Next = tmp->Next;
					} else {
						mpArray[hashKey] = vNull;
					}
					vDelete( tmp );
					mNum--;
					return true;
				}
				prev = tmp;
				tmp = tmp->Next;
			}
			return false;
		}

		/*! \brief Checks if map is empty.
		*
		*
		*	\return True if there is zero elements, false otherwise.
		*/
		inline vBool IsEmpty() const {
			return !mSize;
		}

		/*! \class Iterator.
		 *	\brief Iterates through hash array elements in "random" order.
		 */
		class vIterator {
		public:

			/*! \brief Constructor (the only allowed).
			 *
			 *	Assigns passed hash array as a set to iterate through
			 *	and starts iteration.
			 *
			 *	\param hashArray Hash array.
			 */
			vIterator(vHashMap<TI, TV> &hashArray): mHash(hashArray), mPos(0),	mpList(vNull) {
				Start();
			}

			/*! \brief Begins iteration.
			 */
			vVoid Start() {
				if (mHash.mNum > 0) {
					mPos = 0;
					while (!mHash.mpArray[mPos]) {
						mPos++;
					}
					mpList = mHash.mpArray[mPos];
					return;
				}
				mpList = vNull;
			}

			/*! \brief Moves to next element if possible.
			 */
			vVoid operator ++ () {
				if (mpList) {
					if (mpList = mpList->Next) {
						return;
					}
					mPos++;
				}
				while ((mPos < mHash.mSize) && !mHash.mpArray[mPos]) {
					mPos++;
				}
				if (mPos < mHash.mSize) {
					mpList = mHash.mpArray[mPos];
					return;
				}
				mpList = vNull;
				return;
			}

			/*! \brief Tells whether there's any element at current iterator's position.
			 *
			 *
			 *	\return True if there's, false otherwise.
			 */
			operator vBool() const {
				return mpList != vNull;
			}

			/*! \brief Returns key of current element.
			 *
			 *
			 *	\return Key of current element.
			 */
			TI& Key() const {
				V_CHECK(mpList);
				return mpList->Key;
			}

			/*! \brief Returns value of current element.
			 *
			 *
			 *	\return Value of current element.
			 */
			TV& Value() const {
				V_CHECK(mpList);
				return mpList->Value;
			}

		private:

			vHashMap<TI, TV>&		mHash;	//! Iterator's hash array
			vInt					mPos;	//! key into array of lists
			vElement*				mpList; //! Pointer to element on list
		};

		friend class vIterator;

	private:
		/*! \brief Resizes array to given size.
		*
		*	This causes elements to change their array indices.
		*
		*	\param size New array size.
		*/
		vVoid rehash(const vInt size) {
			vInt i;

			// Move all elements into single list
			vElement* longList = vNull;
			for (i = mSize - 1; i >= 0; i--) {
				if (mpArray[i]) {
					vElement* tmp = mpArray[i];
					while (tmp->Next) {
						tmp = tmp->Next;
					}
					tmp->Next = longList;
					longList = mpArray[i];
				}
			}
			vDeleteArray(mpArray);

			// Upsize array to next power of 2
			vInt newSize = 1;
			while (newSize < size) {
				newSize = newSize << 1;
			}
			vElement** newArray = new vElement*[newSize];
			for (vInt i = 0; i < newSize; i++) {
				newArray[i] = vNull;
			}
			mpArray = newArray;
			mSize = newSize;

			// Move back elements into appropriate lists
			while (longList) {
				vElement* tmp		= longList;
				longList			= longList->Next;
				const vInt hashKey	= HashKey(tmp->Key) & (mSize - 1);
				tmp->Next			= mpArray[hashKey];
				mpArray[hashKey]		= tmp;
			}
		}

	protected:

		vInt		mSize;		//! Size of array of lists
		vElement**	mpArray;	//! Array of lists
		vInt		mNum;		//! Total number of elements on all lists

	};
}

#endif // __VHASH_MAP_H__